package leetcode.to1000;


import java.util.LinkedList;
import java.util.Queue;

public class T0547 {
    class Solution {
        public int findCircleNum(int[][] isConnected) {
            int provinces = isConnected.length;
            boolean[] visited = new boolean[provinces];
            int circles = 0;
            Queue<Integer> queue = new LinkedList<Integer>();
            for (int i = 0; i < provinces; i++) {
                if (!visited[i]) {
                    queue.offer(i);
                    while (!queue.isEmpty()) {
                        int j = queue.poll();
                        visited[j] = true;
                        for (int k = 0; k < provinces; k++) {
                            if (isConnected[j][k] == 1 && !visited[k]) {
                                queue.offer(k);
                            }
                        }
                    }
                    circles++;
                }
            }
            return circles;
        }
    }
    class Solution2 {
        public int findCircleNum(int[][] isConnected) {
            int provinces = isConnected.length;
            boolean[] visited = new boolean[provinces];
            int circles = 0;
            for (int i = 0; i < provinces; i++) {
                if (!visited[i]) {
                    dfs(isConnected, visited, provinces, i);
                    circles++;
                }
            }
            return circles;
        }

        public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {
            for (int j = 0; j < provinces; j++) {
                if (isConnected[i][j] == 1 && !visited[j]) {
                    visited[j] = true;
                    dfs(isConnected, visited, provinces, j);
                }
            }
        }
    }
}
